#include<iostream>
#include<string>
#include<stack>
#include<unordered_map>
using namespace std;

class Solution {
public:
    
    stack<long> num;
    stack<int> ops;
    
    int calculate(string s) {
        int n = s.size();
        
        unordered_map<char,int> m;
        m.insert(make_pair('+',1));
        m.insert(make_pair('-',1));
        m.insert(make_pair('*',2));
        m.insert(make_pair('/',2));
        
        num.push(0);
        while(s.find("(-")!=-1){
            s.replace(s.find("(-"),2,"(0-");
        }
        int i = 0;
        while(i<n){
            if(s[i]=='('){
                ops.push('(');
                i++;
            }else if(s[i]==')'){
                while(ops.top()!='('){
                    cal();
                }
                ops.pop();
                i++;
            }else if(isdigit(s[i])){
                long d = s[i]-'0';
                int t = i+1;
                while(isdigit(s[t])){
                    d = d*10+s[t]-'0';
                    t++;
                }
                num.push(d);
                i = t;
            }else if(s[i]==' '){
                i++;
                continue;
            }else{
                while(!ops.empty() && m[ops.top()] >= m[s[i]]){
                    cal();
                }
                ops.push(s[i]);
                i++;
            }
        }
        while(!ops.empty()){
            cal();
        }
        return num.top();
    }
    void cal(){
        char c = ops.top();
        ops.pop();
        long a = num.top();
        num.pop();
        long b = num.top();
        num.pop();
        switch(c){
            case '+':
                num.push(a+b);
                break;
            case '-':
                num.push(b-a);
                break;
            case '*':
                num.push(a*b);
                break;
            case '/':
                num.push(b/a);
                break;
        }
    }
};

int main(){
    string s="(5-1)*(3+4/2)";
    int ret;
    Solution a;
    cout<<s<<"="<<a.calculate(s)<<endl;
    s="5 * ( 3 + 4 )";
    cout<<s<<"="<<a.calculate(s)<<endl;
    return 0;
}

